﻿/*THÔNG TIN*********************************************************************
 *Tập tin		: Graph_Shortest_Path.h
 *Mô tả			: Thư viện các phương thức tìm đường đi ngắn nhất
 *Ngày tạo		: 03/09/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

/*Lớp các phương thức để tìm đường đi ngắn nhất*/
class PATH : public GRAPH	{
private:
	// Mảng lưu đỉnh trước trong khi duyệt
	vector <uint16_t> before;
	// Mảng lưu độ dài đường đi từ source đến đỉnh i
	vector <double> min_len;

public:
	// Phương thức khởi tạo
	PATH();

	// Khởi tạo cho thuật toán Dijkstra
	void Initiate_Dijkstra();
	// Thuật toán Dijkstra tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trên đồ thị bất kỳ
	void Dijkstra();
	//Lưu đường đi vào mảng result
	void Build_result();
	// In kết quả tìm đường đi ngắn nhất ra file .out
	void Print_result_to_out(string input_file);
	// In kết quả đường đi ngắn nhất ra file .dot
	void Print_result_to_dot(string input_file);
};/*Kết thúc khai báo lớp PATH*/

/*Phương thức khởi tạo*/
PATH :: PATH()	{
	before.clear();
	min_len.clear();
}/*Kết thúc phương thức PATH*/

/*Khởi tạo cho thuật toán Dijkstra*/
void PATH :: Initiate_Dijkstra()	{
	Random_source_and_target();

	// Khởi tạo các mảng final, before, min_len
	final.resize( Get_vertices() );
	final[Get_source()] = true;

	before.resize( Get_vertices() );
	fill(before.begin(), before.end(), Get_source());
	before[Get_source()] = UINT16_MAX;

	min_len.resize( Get_vertices() );
	for (uint16_t i=0; i<Get_vertices(); ++i)
		min_len[i] = Get_length(Get_source(), i);	

	cout << "Thuc hien thuat toan Dijkstra..........";
	start_time = clock();
}/*Kết thúc phương thức Initiate_Dijkstra*/

/*Thuật toán Dijkstra tìm đường đi ngắn nhất giữa 2 đỉnh bất kỳ trên đồ thị bất kỳ*/
void PATH :: Dijkstra()	{
	uint16_t i, j;

	do	{
		double min = double(UINT16_MAX);
		i = UINT16_MAX;

		/*Tìm trong các đỉnh lân cận j đỉnh nào gần đỉnh 0 nhất*/
		for (j=0; j<Get_vertices(); ++j)	{
			if (!final[j])
				if (min>min_len[j])	{
					min = min_len[j];
					i = j;
			}
		}

		// Kết thúc khi không tìm được đỉnh j nào hoặc đã tìm được đến đích
		if (i==UINT16_MAX || i==Get_target())
			break;

		// Đánh dấu đỉnh i đã xét xong
		final[i] = true;

		// Tối ưu đường đi và lưu vết đường đi
		for (j=0; j<Get_vertices(); ++j)
			if (!final[j])
				if (min_len[j] > min_len[i] + Get_length(i, j))	{
					min_len[j] = min_len[i] + Get_length(i, j);
					before[j] = i;
			}
	} while (true);

	Print_runtime();
}/*Kết thúc phương thức Dijkstra*/

/*Lưu đường đi vào mảng result*/
void PATH :: Build_result()	{
	if (min_len[Get_target()] != UINT16_MAX)	{
		result.push_back(Get_target());

		uint16_t i = Get_target();

		while (before[i] != UINT16_MAX)	{
			i = before[i];
			result.push_back(i);
		}
	}
}/*Kết thúc phương thức Build_result*/

/*In kết quả tìm kiếm đường đi ra file .out*/
void PATH :: Print_result_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Dijkstra", ".out");

	if (min_len[Get_target()] == UINT16_MAX)
		f << "Khong co duong di tu " << Get_source()+1 << " den " 
		  << Get_target()+1 << ".\n";
	else	{
		f << "Do dai duong di ngan nhat tu " << Get_source()+1 << " den " 
		  << Get_target()+1 << " la " << min_len[Get_target()] << ".\n"
		  << "Duong di la: \n";

		for (uint16_t i=result.size()-1; i!=0; --i)
			f << result[i]+1 << "--(" << Get_length(result[i], result[i-1]) << ")-->";

		f << result[0] + 1 << "\n";
	}

	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_result_to_out*/

/*In kết quả đường đi ngắn nhất ra file .dot*/
void PATH :: Print_result_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Dijkstra", ".dot");

	f << "digraph " << input_header << "_Dijkstra {\n";

	if (min_len[Get_target()] == UINT16_MAX)	{
		f << "label = \"\\n\\nKhong co duong di tu " << Get_source() + 1 << " den " 
		  << Get_target() + 1 << " voi du lieu tu file " << input_file << ".\"\n}";
	}
	else	{
		for (uint16_t i=0; i<Get_vertices(); ++i)
			for (uint16_t j=0; j<Get_vertices(); ++j)	{
				if (Get_length(i, j) != UINT16_MAX)	{
					f << i+1 << " -> " << j+1 << " [";

					uint16_t k;

					for (k=result.size()-1; k!=0; --k)
						if (result[k] == i && result[k-1] == j)
							break;

					if (k == 0)
						f << "style = dotted, ";

					f << "label = \"" << Get_length(i, j) << "\"]\n";
				}
			}

		f << "label = \"\\n\\nDuong di ngan nhat dung thuat toan "
		  << "Dijkstra voi du lieu tu file " << input_file << "\\n"
		  << "Do dai duong di ngan nhat tu " << Get_source() + 1 << " den " 
		  << Get_target()+1 << " la " << min_len[Get_target()] << ".\"\n}";
	}	

	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_result_to_dot*/
